10224. Точки сочленения – расстановка меток

Задан неориентированный граф. Запустите поиск в глубину из заданной вершины v. Выведите метки d[v] и up[v] для каждой вершины v в порядке возрастания вершин.

Вход. Первая строка содержит количество вершин n (n ≤ 100) и ребер m неориентированного графа. Вершины нумеруются начиная с 1. Каждая из следующих m строк содержит две вершины a и b – неориентированное ребро графа. Последняя строка содержит вершину v.

Выход. Запустите dfs(v). Выведите метки d[v] и up[v] для каждой вершины v (v = 1, 2, ..., n). Метки для каждой вершины следует выводить в отдельной строке.

Пример входа 1	Пример выхода 1
6 8 6 5 6 3 5 3 4 5 3 4 3 2 1 2 1 3 1	1 1 2 1 3 1 4 3 5 3 6 3
Пример входа 2	Пример выхода 2
7 9 1 2 2 3 1 3 3 4 2 5 4 5 4 6 4 7 6 7 1	1 1 2 1 3 1 4 2 5 2 6 4 7 4

РЕШЕНИЕ

графы – точки сочленения

Анализ алгоритма

Метки d[v] / up[v] используются при поиске точек сочленения. Совершим поиск в глубину и расставим указанные метки.

Пример

Расставим метки в графах, приведенных в первом и во втором тестах.

Реализация алгоритма

Объявим матрицу смежности графа g и рабочие массивы used, d и up.

#define MAX 101

int g[MAX][MAX];

int used[MAX], d[MAX], up[MAX];

Функция dfs совершает поиск в глубину с расстановкой меток d[v] и up[v].

void dfs(int v, int p = -1)

{

used[v] = 1;

d[v] = up[v] = tm++;

for (int i = 1; i <= n; i++)

{

if (g[v][i] == 0) continue;

if (i == p) continue;

if (used[i])

up[v] = min(up[v], d[i]);

else

{

dfs(i, v);

up[v] = min(up[v], up[i]);

}

}

}

Основная часть программы. Читаем входные данные. Заполняем матрицу смежности графа g.

scanf("%d %d", &n, &m);

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

g[a][b] = g[b][a] = 1;

}

Читаем вершину v и запускаем из нее поиск в глубину.

scanf("%d", &v);

tm = 1;

dfs(v);

Выводим метки d[v] и up[v] для каждой вершины.

for (i = 1; i <= n; i++)

printf("%d %d\n", d[i], up[i]);